package com.zdp.leetcode;

public class 黑白方格画 {
    public static void main(String[] args) {
        Solution1 demo = new Solution1();
        demo.paintingPlan2(3,8);

    }
}
class Solution1 {
    public int paintingPlan(int n, int k) {
        //先算出所要用到的行和列
        int result = 0;
        if(k==0||k==n*n){
            return 1;
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(n*(i+j)-i*j==k){
                    //找到行和列，就计算他们的组合 C(n,i) C(n,j)
                    System.out.println("i = "+i+" j ="+j);
                    result = result +  C(n,i)*C(n,j);
                }
            }
        }
        return result;
    }
    //比较快
    public int paintingPlan2(int n, int k) {
        //先算出所要用到的行和列
        int result = 0;
        if(k==0||k==n*n){
            return 1;
        }
        //根据公式 和i 倒推出j的公式  ===> n*(i+j)-i*j = k
        //===> j = (k-n*i)/(n-i)
        for(int i=0;i<n;i++){
            float j =(float) (k-n*i)/(n-i);
            if(j==(int)j){
                result += C(n,i)+C(n,(int)j);
            }
        }
        return result;
    }
    public int C(int n,int k){
        int a=1;
        int b=1;
        int c=1;
        for(int i=1;i<=n;i++)
            a *= i;
        for(int i=1;i<=(n-k);i++)
            b *= i;
        for(int i=1;i<=k;i++)
            c *=i;
        return a/(b*c);
    }
}
/*
* 题目描述：
* 小扣注意到秋日市集上有一个创作黑白方格画的摊位。摊主给每个顾客提供一个固定在墙上的白色画板，画板不能转动。画板上有 n * n 的网格。绘画规则为，小扣可以选择任意多行以及任意多列的格子涂成黑色，所选行数、列数均可为 0。

小扣希望最终的成品上需要有 k 个黑色格子，请返回小扣共有多少种涂色方案。

注意：两个方案中任意一个相同位置的格子颜色不同，就视为不同的方案。

示例 1：

输入：n = 2, k = 2

输出：4

解释：一共有四种不同的方案：
第一种方案：涂第一列；
第二种方案：涂第二列；
第三种方案：涂第一行；
第四种方案：涂第二行。

示例 2：

输入：n = 2, k = 1

输出：0

解释：不可行，因为第一次涂色至少会涂两个黑格。

示例 3：

输入：n = 2, k = 4

输出：1

解释：共有 2*2=4 个格子，仅有一种涂色方案。

限制：

1 <= n <= 6
0 <= k <= n * n

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ccw6C7
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
